package 剑指Offer._3140;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/9/2 9:11
 * 栈的压入、弹出序列
 * 算法：栈  模拟
 * 遍历 popped，如果 pushed 当前元素跟 popped 当前元素不相等的话，就入栈 --- 相等表示元素刚入栈就出栈
 * 如果栈顶元素跟 popped 当前元素相等，就出栈，跳过 --- 表示元素出栈
 * 当 pushed 循环完之后，遍历栈中元素，看跟 popped 中剩余的元素是否相等
 */
public class _31 {
    public static void main(String[] args) {
        int[] pushed = new int[]{2, 1, 0};
        int[] popped = new int[]{1, 2, 0};
        System.out.println(new _31().validateStackSequences(pushed, popped));
    }

    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> stack = new LinkedList<>();
        int i = 0, j = 0, n = pushed.length;
        while (i < n && j < n) {
            if (!stack.isEmpty() && popped[i] == stack.peek()) {
                stack.pop();
                ++i;
            } else {
                if (pushed[j] != popped[i]) stack.push(pushed[j]);
                else ++i;
                ++j;
            }
        }
        for (; i < n; i++) if (popped[i] != stack.pop()) return false;
        return true;
    }

}
